package com.leecode.xiehf.page_01;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 * <p>
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * [1,1,48,50,99,100,103,333,333]
 * 250
 */
public class Solution_0016 {

    public static void main(String[] args) {
        Solution_0016 solution_0016 = new Solution_0016();
        int result = solution_0016.threeSumClosest(new int[]{1, 1, 48, 50, 99, 100, 103, 333, 333}, 250);
        System.out.println(result);
    }

    public int threeSumClosest(int[] nums, int target) {
        int length = nums.length;
        Arrays.sort(nums);
        int total = nums[0] + nums[1] + nums[length - 1];
        if (length == 3) {
            return total;
        }
        if (total == target) {
            return target;
        }
        for (int i = 0; i < length - 2; i++) {
            int j = i + 1;
            int k = length - 1;
            while (j < k) {
                int min = nums[i] + nums[j] + nums[j + 1];
                if (min > target) {
                    // 最小的数都大于target，所以其他的数更加大于target，差值更大
                    if (Math.abs(min - target) < Math.abs(total - target)) {
                        total = min;
                    }
                    break;
                }
                int max = nums[i] + nums[k - 1] + nums[k];
                if (max < target) {
                    // 最大的数都小于target 所以其他的数肯定更加小于target 差值更远
                    if (Math.abs(max - target) < Math.abs(total - target)) {
                        total = max;
                    }
                    break;
                }
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    return target;
                }
                if (Math.abs(sum - target) < Math.abs(total - target)) {
                    total = sum;
                }
                if (sum > target) {
                    k--;
                    while (k > j && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else {
                    j++;
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                }
            }
        }
        return total;
    }
}
